package main.leetcode.clockin.March;

import java.util.Arrays;

/**
 * 820.单词的压缩编码
 *
 * <p>给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
 *
 * <p>例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
 *
 * <p>对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
 *
 * <p>那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
 *
 * <p>
 *
 * <p>示例：输入: words = ["time", "me", "bell"] 输出: 10 说明: S = "time#bell#" ， indexes = [0, 2, 5] 。
 *
 * <p>提示：1 <= words.length <= 2000 1 <= words[i].length <= 7 每个单词都是小写字母 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/short-encoding-of-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day28 {
    public static void main(String[] args) {
        System.out.println(
                new day28().minimumLengthEncoding(new String[] {"time", "atime", "btime"}));
    }
    // 后缀
    //    public int minimumLengthEncoding(String[] words) {
    //        Set<String> set = new HashSet<>(Arrays.asList(words));
    //        for (String word : words)
    //            for (int i = 1; i < word.length(); ++i) set.remove(word.substring(i)); // 移除后缀
    //        int ans = 0;
    //        for (String word : set) {
    //            ans += word.length() + 1; // 1 for '#'
    //        }
    //        return ans;
    //    }

    // （伪）反转 + 排序
    public int minimumLengthEncoding(String[] words) {
        int n = words.length;

        // 排序
        Arrays.sort(
                words,
                // 重写字符串比较方法（后缀比较
                (s1, s2) -> {
                    int n1 = s1.length();
                    int n2 = s2.length();
                    int res;
                    for (int i = 0; i < Math.min(n1, n2); ++i) {
                        res = Character.compare(s1.charAt(n1 - 1 - i), s2.charAt(n2 - 1 - i));
                        if (res != 0) return res;
                    }
                    return Integer.compare(n1, n2);
                });
        int ans = 0;
        for (int i = 0; i < n; ++i)
            if (i + 1 < n && words[i + 1].endsWith(words[i])) {
            } // 当前单词是后者的后缀
            else ans += words[i].length() + 1;

        return ans;
    }

    // 字典树
    //    public int minimumLengthEncoding(String[] words) {
    //        TrieNode trie = new TrieNode();
    //        Map<TrieNode, Integer> nodes = new HashMap<>();
    //        String word;
    //        TrieNode cur;
    //        for (int i = 0; i < words.length; ++i) {
    //            word = words[i];
    //            cur = trie; // 回到根节点
    //            for (int j = word.length() - 1; j >= 0; --j)
    //                cur = cur.get(word.charAt(j)); // 构建字典树枝并返回尾结点
    //            nodes.put(cur, i); // 存入 首字母结点-下标
    //        }
    //
    //        int res = 0;
    //        for (TrieNode node : nodes.keySet()) {
    //            if (node.count == 0) // 选取叶子结点
    //            res += words[nodes.get(node)].length() + 1;
    //        }
    //        return res;
    //    }

    private class TrieNode {
        TrieNode[] children;
        int count;

        private TrieNode() {
            children = new TrieNode[26];
            count = 0;
        }

        private TrieNode get(char c) {
            if (children[c - 'a'] == null) {
                children[c - 'a'] = new TrieNode();
                ++count;
            }
            return children[c - 'a'];
        }
    }
}
